//如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。 
//
// 
// 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。 
// 
//
// 
// 
// 给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。 
//
// 子数组 是数组中的一个连续序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3,4]
//输出：3
//解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 5000 
// -1000 <= nums[i] <= 1000 
// 
// 
// 
// Related Topics 数组 动态规划 
// 👍 388 👎 0

package com.cute.leetcode.editor.cn;
public class ArithmeticSlices {
    public static void main(String[] args) {
        Solution solution = new ArithmeticSlices().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 通过等差数列的长度L可以求出所有长度>=3的数列的个数为 (L-1)*(L-2)/2
     * 比如1 2 3 4 长度为4 然后可以得到的数列有 1 2 3   2 3 4   1 2 3 4 即3个数列
     * 所以一种方法（题解1）可以统计最长的长度L，发现不是的话需要移动下标到新的起始位置
     * 并且重置L的长度为2（最少有两个元素才存在差值）
     *
     */
    class Solution {

        /**
         * 使用DP的方法实现，dp[i]存储的是以nums[i]结尾且长度大于等于 3 的连续等差数列的个数
         * 状态转移方程dp[i] = dp[i-1] + 1
         * 每次只需要判断新的数字和前边的数列是否为等差即可
         */
        public int S2numberOfArithmeticSlices(int[] nums) {
            if (nums.length <= 2) return 0;
            int len;
            len = nums.length;
            int[] dp = new int[len];
            int res = 0;
            for (int i = 2; i < len; i++) {
                if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]){
                    dp[i] = dp[i-1]+1;
                    res += dp[i];
                }
            }
            return res;
        }

        /**
         * 题解1，使用滑动窗口的方式进行统计(更新下标)
         */
        public int numberOfArithmeticSlices(int[] nums) {
            if (nums.length <= 2) return 0;
            int len;
            len = nums.length;
            int preDiff = nums[1]-nums[0];
            int L = 2;
            int res = 0;
            for (int i = 2; i < len; i++) {
                int curDiff =nums[i] - nums[i-1];
                if (curDiff == preDiff)//是等差数列就长度++
                    L++;
                else {//不是等差数列就进行新的等差数列的判断
                    res += (L-2)*(L-1)/2;
                    L = 2;
                    preDiff = curDiff;
                }
            }
            res += (L-2)*(L-1)/2;//最后进行一次累加
            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}